%{
#include "dfa.h"
int yylex();
extern int yyparse();
void yyerror(const char* s);
extern void nfa2dfa();
nfa Nfa;
Edge e[maxn];
%}

%token CHAR //[a-zA-Z0-9]
%token OR //|
%token STAR //*
%token LPAREN //(
%token RPAREN //)
%token END //' ''\t''\n'

%%
lines :    lines regex END { Nfa.PrintNfa();nfa2dfa();return 0;} 
      |    lines END
      |
      ;
regex   : term	            { $$=$1;}
	| term OR regex     { Nfa.create_nfa_alternation();} 
        ;

term    : factor            { $$ = $1; }   
        | factor term       { Nfa.create_nfa_concatenation();}
        ;

factor  : atom              { $$ = $1; }   
        | atom STAR        {Nfa.create_nfa_closure();}                      
        ;

atom    : CHAR              { Nfa.create_nfa_atom($1); }
	| LPAREN regex RPAREN                        
        ;

%%
int yylex(){
    int t;
    while(1){
        t=getchar();
        if(t==' '||t=='\t'||t=='\n'){
            return END;
        }
        else if((t >= 'a' && t <= 'z') || (t >= 'A' && t <= 'Z')||(t >= '0' && t <= '9')) {
            yylval = t;
            return CHAR;  
        }
	else if(t=='|') {
            return OR;  
        }
        else if(t=='*'){
            return STAR;
        }
        else if(t=='('){
            return LPAREN;
        }
        else if(t==')'){
            return RPAREN;
        }
        else {
            return t;
        }
    }
}

void yyerror(const char* s){
    cout<<"Parse error:"<<s<<endl;
    return ;
}

int main()
{
    yyparse();
    return 0;
}

void nfa2dfa() {
    int cntEdge = 0;
    int startNode;
    int* endNode = 0, * node = 0;
    vector<char> Char;
    int nodeCount = 0, endCount = 0, charCount = 0;
    int cntRealEdge[maxn] = { 0 };
    //input
    startNode=atoi(Nfa.st.top().begin.c_str());
    endCount=1;
    endNode = new int[endCount];
    for (int i = 0; i < endCount; i++)
    	endNode[i]=atoi(Nfa.st.top().end.c_str());
    while (!Nfa.NfaEdge.empty()) {
    	Edge ed = Nfa.NfaEdge.front();
    	e[cntEdge].begin=ed.getBegin();
    	e[cntEdge].letter=ed.getletter();
    	e[cntEdge].end=ed.getEnd();
    	cntEdge++;
    	Nfa.NfaEdge.pop();
   }
        //Find all the char
    set<char> nodeChar;
    for (int i = 0; i < cntEdge; i++)
        if (e[i].getletter() != '#')
            nodeChar.insert(e[i].getletter());
    charCount = nodeChar.size();
    Char.resize(charCount);
    copy(nodeChar.begin(), nodeChar.end(), Char.begin());

    // Find all the nodes
    set<int> nodes;
    for (int i = 0; i < cntEdge; i++) {
        nodes.insert(stoi(e[i].begin));
        nodes.insert(stoi(e[i].end));
    }
    nodeCount = nodes.size();
    node = new int[nodeCount];
    copy(nodes.begin(), nodes.end(), node);

    // Convert NFA to DFA
    vector<State*> allSet;
    vector<Relation*> rel;
    vector<string>stringRel;
    State* startSet = new State();
    startSet->set(startNode);
    getEClosure(e, cntEdge, startSet);
    allSet.push_back(startSet);
    for (int i = 0; i < allSet.size(); i++)
    {
        for (auto ch : Char)
        {
            Relation* r = new Relation();
            State* newSet = new State();
            moveT(ch, e, cntEdge, allSet[i], newSet);
            getEClosure(e, cntEdge, newSet);
            if (newSet->getLength() > 0)
            {
                if (isInsertForRel(rel, allSet[i], ch, newSet))
                {
                    string s = "";
                    r->preState = allSet[i];
                    r->inputChar = ch;
                    r->nextState = newSet;
                    rel.push_back(r);
                    int num = isInsert(allSet, newSet);
                    if (num == allSet.size())
                        allSet.push_back(newSet);
                    s.push_back('A' + i); s.append(" "); s.push_back(ch); s.append(" "); s.push_back('A' + num); s.push_back('\n');
                    stringRel.push_back(s);
                }
            }
        }
    }
    vector<char> Start, End;
    for (int i = 0; i < allSet.size(); i++)
    {
        if (allSet[i]->find(startNode))
            Start.push_back('A' + i);
        for (int j = 0; j < endCount; j++)
            if (allSet[i]->find(endNode[j]))
                End.push_back('A' + i);
    }
    cout << "DFA:"<<endl;
    cout << "开始状态: {";
    for (auto s : Start)
        cout << s << " ";
    cout << "}\n";
    cout << "终态: {";
    for (auto s : End)
        cout << s << " ";
    cout << "}\n";
    for (auto s : stringRel)
        cout << s;

    // Clean up memory
    delete[] endNode;
    delete[] node;
    for (auto s : allSet)
        delete s;
    for (auto r : rel)
        delete r;
    return ;
}




